package Search;

import Algorithm.Sort.RadixSort;
import Algorithm.Sort.Template;
import Utils.ArrUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 查找(3)
 * 插值查找
 * 只有 mid的计算和二分查找不一样 还有mid判断是否越界(且优化)
 */
public class InsertSearch {
    private static List<Integer> result = new ArrayList<>();

    public static List<Integer> search(int[] arr, int left, int right, int target) {
        //递归结束条件：left>right 但没有找到目标值  mid判断是否越界
        if (left > right || target < arr[0] || target > arr[arr.length - 1]) return result;

        int mid = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if (target > midVal) return search(arr, mid + 1, right, target);//右侧递归
        else if (target < midVal) return search(arr, left, mid - 1, target);//左侧递归
        else {//相等
            result.add(mid);
            int temp = mid - 1;
            while (true) {//左边扫描 添加右边与之相同的值
                if (temp < 0 || arr[temp] != target) break;//下标越界或不为目标值
                result.add(temp);//添加下标
                temp -= 1;//左移
            }
            temp = mid + 1;//右边扫描 添加右边与之相同的值
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != target) break;//下标越界或不为目标值
                result.add(temp);//添加下标
                temp += 1;//右移
            }
            return result;//返回下标集合
        } //else
    }


    public static void main(String[] args) {
        int testSize = 20;
        int[] arr = Template.getIntData(testSize);
        //输出原数组
        ArrUtil.show(arr);
        RadixSort.sort(arr);//需要目标数组有序 调用基数排序
        ArrUtil.show(arr);
        int a = (int) (Math.random() * testSize);

        System.out.println("插值查找" + a);

        List<Integer> index = search(arr, 0, arr.length - 1, a);

        System.out.println("下标" + index);
    }
}
